An upper bound on the feedback capacity of unifilar finite-state channels(FSCs) is derived. A new technique, called the $Q$-contexts, is based on aconstruction of a directed graph that is used to quantize recursively thereceiver's output sequences to a finite set of contexts. For any choice of$Q$-graph, the feedback capacity is bounded by a single-letter expression,$C_\text{fb}\leq \sup I(X,S;Y|Q)$, where the supremum is over $P_{X|S,Q}$ andthe distribution of $(S,Q)$ is their stationary distribution. It is shown thatthe bound is tight for all unifilar FSCs where feedback capacity is known:channels where the state is a function of the outputs, the trapdoor channel,Ising channels, the no-consecutive-ones input-constrained erasure channel andfor the memoryless channel. Its efficiency is also demonstrated by deriving anew capacity result for the dicode erasure channel (DEC); the upper bound isobtained directly from the above expression and its tightness is concluded witha general sufficient condition on the optimality of the upper bound. Thissufficient condition is based on a fixed point principle of the BCJR equationand, indeed, formulated as a simple lower bound on feedback capacity ofunifilar FSCs for arbitrary $Q$-graphs. This upper bound indicates that asingle-letter expression might exist for the capacity of finite-state channelswith or without feedback based on a construction of auxiliary random variablewith specified structure, such as $Q$-graph, and not with i.i.d distribution.The upper bound also serves as a non-trivial bound on the capacity of channelswithout feedback, a problem that is still open.
展开▼
